Clustering is the partitioning of data into groups such that similar data objects belong to the same group and dissimilar objects to different groups according to some measure of similarity. The detection of clusters of data points is of significant interest when analysing large data sets. In some data sets, particularly those derived from business applications, the data set to be analysed is not fixed once and forever, but as time goes by additional data is added to the data set. This change in the data set may mean that the cluster model should be revised. Furthermore, by considering the temporal dimension it may be possible to carry out a more rigorous analysis. For example, consider two clusters that are moving along intersecting paths within a two-dimensional plane. If the temporal analysis is discarded then the intersecting clusters may appear to be a single connected cluster, rather than two unconnected clusters that happen to intersect at a given point in time.
A system that can detect the formation and/or variation in clusters can be used to build systems for the early detection of patterns of abnormal usage of communications networks, amongst other things. Such abnormal network usage includes, but is not limited to:                Illegal or malicious activities: These are activities intentionally carried out without the permission of the network owner in order to gain access to network resources or to damage the network and connected devices.        Novel network user activities: These are activities which are carried out by a user and permitted by the network owner but show novel characteristics when compared to the usage history or when compared to the network usage specification.        Activities due to faulty equipment: These are network activities caused by faulty or otherwise malfunctioning network equipment.        
The state of a network can be analysed by network statistics recorded by sensors from the network. Such statistics can be, for example, bandwidth utilization, packet drop rate, number of users connected to a wireless hub, or the average traffic caused by premium users, etc. Each of the above activities causes certain patterns in the statistics taken from a computer network. This means, for the same activity a subset of the statistics are very likely to have similar values. They therefore form clusters which can be detected by cluster algorithms. However, the above mentioned activities are quite rare and so are the clusters. Furthermore, it is very difficult to distinguish whether a certain cluster just happens by chance, for example due to a random peak in network utilization, or systematically, for example, because a new exploit has been developed that gives unrestricted access to a wireless hot spot without paying. On the other hand, it is very important to detect any of the above activities in its earliest stages to take suitable countermeasures. Early stages, in this context, means detecting very small clusters in a rather noisy environment. This, however, is not possible with existing clustering approaches.
Furthermore, there has recently been increased interest in so-called local patterns rather than the global structure of the data, as the global data structure is much better known by domain experts and therefore not considered as interesting and small data structures may indicate niches or upcoming trends which may be of significant interest or value.
The difficulty with analysing local patterns is, however, that quite often large numbers of patterns are ‘discovered’ by some data mining technique (e.g. association rules) but most of them prove to be uninteresting or incidental on closer inspection. In practise this means that quite often a lot of time is wasted on scanning these useless patterns and the whole data mining effort is put into question.
There are two different approaches to the notions of ‘moving cluster’. The real world objects that make up the cluster may change as a whole and if we observe the objects at some later point in time we will find a different cluster position. This approach requires some kind of object ID to match different data objects to the same real world object in order to capture the change (Li et al, “Clustering moving objects”, Proc. 10th ACM SIGKDD Int. Conf. on Knowl. Discovery and Data Mining, pages 617-622, 2004 and Kalnis et al, “On discovering moving clusters in spatio-temporal data”, Proc. 9th Int. Conf. Scientific and Statistical Database Management, vol. 3633 of LNCS, pages 236-253, 2005).
The second notion of a ‘moving cluster’ is that the cluster itself changes but not necessarily the individual real world objects represented by the cluster (CC Aggarwal et al, “A framework for clustering evolving data streams”, Proc. 29th Int. Conf. on Very Large Databases, pages 81-92, 2003). As an example, the cluster of ‘young people with frequent phoning behaviour’ may change over time; that is, new customers may expose a different phoning behaviour than existing customers, changing slowly the characteristics of the cluster. This is the kind of ‘moving clusters’ that are addressed in the present invention.